#include <stdio.h>
#include <stdlib.h>
void Heapsort(int a[],int n)
{
	int *D;
	int end,p,tag;
	D=(int *)malloc((n+1)*sizeof(int));
	for(int i=0;i<n;i++)
		D[i+1]=a[i];
	end=n;
	while(end-1)
	{
		while(1)
		{
			p=end/2;
			tag=0;
			while(p)
			{
				if(D[p]<D[2*p])
				{
					D[0]=D[p];
					D[p]=D[2*p];
					D[p*2]=D[0];
					tag=1;
				}
				if(2*p+1<=end&&D[p]<D[2*p+1])
				{
                    D[0]=D[p];
					D[p]=D[2*p+1];
					D[p*2+1]=D[0];
					tag=1;
				}
				p--;
			}
			if(!tag)
					break;
		}
		D[0]=D[1];
		D[1]=D[end];
		D[end]=D[0];
		end--;
	}
	for(int i=0;i<n;i++)
	{
		a[i]=D[i+1];
	}

	free(D);
}
int main()
{
	int n;
    int a[8]={3,2,5,8,5,7,6,9};
	Heapsort(a,8);
	for(int i=0;i<8;i++)
		printf("%5d",a[i]);
	printf("\n");
	return 0;
}


